2021 操作系统王道考研

第一章计算机系统概述
- 01 操作系统的概念（定义）
  - 概念（定义）
    
    负责管理协调硬件、软件等计算机资源的工作
    
    为上层用户、应用程序提供简单易用的服务
    
    是一种系统软件
  - 资源的管理者
    
    处理及管理
    
    存储管理
    
    文件管理
    
    设备管理
  - 命令接口
    
    联机命令接口
    
    直接在命令行输入
    
    脱机命令接口
    
    写命令脚本
- 02 操作系统的四个特征
  - 操作系统的特征
    
    并发（Concurrence）——最基本的特征
    
    概念：指两个或多个事件在同一时间间隔内发生。这些时间宏观上是同时发生的，微观上是交替发生的。
    
    并行：指两个或多个事件在同一时刻同时发生。
    
    单核与多核
    
    单核CPU同一时刻只能运行一个程序，并发执行程序
    
    多核CPU同一时刻可以执行多个程序，并行执行程序
    
    共享（Sharing）——最基本的特征，二者互为存在条件
    
    概念：即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。
    
    两种资源共享方式
    
    互斥共享方式
    
    一个时间段内只允许一个进程访问该资源啊
    
    例子：摄像头，QQ和微信不能同时使用
    
    同时访问方式
    
    允许一个时间段内由多个进程“同时”对他们进行访问（宏观同时）
    
    例子：发送文件、扬声器（真同时）
    
    如果失去并发性，系统中只有一个程序正在运行，共享性失去意义。
    
    如果失去共享性，QQ和微信不能同时访问硬盘资源，无法实现同时发送文件，也就无法并发。
    
    虚拟（Virtual）
    
    概念：把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。
    
    虚拟存储器技术，内存划分给多个程序使用：虚拟技术中的“空分复用技术”
    
    虚拟处理器，处理器被多个程序使用：虚拟技术中的“时分复用”技术，微观上交替执行。
    
    没有并发性，也就谈不上虚拟性
    
    异步（Asynchronism）
    
    概念：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进。
    
    如果失去并发性，系统只能串行执行各个程序，当程序执行完毕后才会归还。只有系统拥有并发性，才有可能导致异步性。
- 03 OS的发展与分类
  - 手工操作阶段
    
    纸带
    
    输入输出速度较慢，处理速度快，用户独占全机，人机速度矛盾，导致资源利用率极低
  - 批处理阶段
    
    单道批处理系统
    
    主要特征
    
    自动性，磁带上的作业能自动逐个运行
    
    顺序性，作业的完成顺序与进入内存的顺序应完全相同
    
    单道性，内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存运行，当该程序完成或发生异常时，才换入其后继程序进入内存运行。
    
    外围机
    
    引入脱机输入/输出技术（用外围机+磁带），并由监督程序负责控制作业的输入、输出
    
    监督程序——操作系统的雏形
    
    优点
    
    缓解人及速度矛盾，提升资源利用率
    
    缺点
    
    内存中只能有一道程序运行
    
    CPU有大量时间是在空闲等待I/O完成，利用率依然较低
    
    多道批处理系统（操作系统开始出现）
    
    优点
    
    多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持“忙碌”状态，系统吞吐量增大。
    
    缺点
    
    没有人机交互功能，提交作业后只能等待计算机处理，无法对中间过程进行干预，比如调试，输入参数
    
    工作示意图
  - 分时操作系统
    
    概念：计算机以时间片为单位轮流为每个用户/作业服务，各个用户可通过终端与计算机进行交互。
    
    优点
    
    用户的请求可以被即时相应，解决了人机交互问题。
    
    允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。
    
    用户感觉独占全机
    
    缺点
    
    不能优先处理紧急任务。
    
    操作系统对每个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务点而紧急行。
  - 实时操作系统
    
    计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。
    
    优点
    
    能够响应一些紧急任务，某些紧急任务不需时间片排队。
    
    硬实时系统
    
    必须在绝对严格的规定时间内完成处理。
    
    （导弹控制系统、自动驾驶系统
    
    软实时系统
    
    能接受偶尔违反事件规定
  - 网络操作系统
    
    把网络中的各个计算机有机地结合起来，实现数据传输等功能。
    
    实现网络中各种资源的共享（如文件共享）和个台计算机之间的通信。
    
    Windows NT就是一种典型的网络操作系统，网站服务器就可以使用。
  - 分布式操作系统
    
    主要特点是：分布性和并行性。
    
    系统中各台计算机地位相同，任何工作都可以用分布在这些计算机上，由它们并行、协同完成这个任务。
  - 个人计算机操作系统
    
    Windows XP、MacOS
- ⭐04 操作系统的运行机制
  - 程序是如何运行的
    
    C语言代码➡编译➡机器指令（二进制）
    
    CPU执行机器指令
  - 两种程序
    
    内核程序
    
    执行一些特权指令
    
    应用程序
    
    只能执行非特权指令
  - 两种指令
    
    特权指令
    
    如：内存清零指令，这些指令影响重大，只允许管理者（操作系统内核）使用。
    
    非特权指令
    
    如：加法指令、减法指令。
  - 两种处理器状态
    
    用于区分此时正在运行的是内核程序 or 应用程序
    
    内核态（核心态、管态）
    
    运行的是内核程序
    
    可以执行特权指令
    
    用户态（目态）
    
    运行的是应用程序
    
    只能执行非特权指令
    
    如何区分这两种状态？
    
    CPU中的PSW寄存器（程序状态字寄存器），其中有个二进制位，1表示“内核态”，0表示“用户态”
    
    ⭐两种状态的切换
    
    内核态➡用户态
    
    执行一条特权指令——修改PSW的标志位为用户态，操作系统主动让出CPU控制权
    
    用户态➡内核态
    
    由“中断”引发，CPU 硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回CPU的使用权
- 05 中断和异常
  - 中断的作用
    
    中断会使CPU由用户态变为内核态，使操作系统重新夺回对CPU的控制权
    
    如果没用中断机制，就无法进行并发
    
    中断是操作系统内核夺回CPU使用权的唯一途径
  - 中断的类型
    
    内中断（也称异常、例外）
    
    与当前执行的指令有关，中断信号来源于CPU内部
    
    由某个指令引发的中断
    
    陷阱、陷入（trap）
    
    由陷入指令引发的，是应用程序故意引发的
    
    如：系统调用
    
    故障（fault）
    
    由错误条件引起，可能被内核程序修复。
    
    如：缺页故障
    
    终止（abort）
    
    由致命错误引起，内核程序无法修复该错误。
    
    如：整数除0、非法使用特权指令
    
    外中断（也称中断）
    
    与当前执行的指令无关，中断信号来源于CPU外部
    
    时钟中断
    
    由时钟部件发来的中断信号
    
    时钟部件每隔一个时间片，归给CPU发送一个时钟中断信号
    
    I/O中断
    
    由输入输出设备发来的中断信号
  - 中断机制的基本原理
    
    不同的中断信号，需要用不同的中断处理程序来处理
    
    内中断：CPU在执行指令时会检查是否有异常发生
    
    外中断：每个指令周期末尾，CPU都会检查是否有外中断信号需要处理。
    
    中断向量表
    
    CPU检测到中断后，根据中断信号的类型去查询中断向量表，找到相应的中断处理程序（运行在内核态）在内存中的存放位置
- 06 系统调用
  - 什么是系统调用？
    
    概念：操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用系统调用的特殊函数，应用系统可以通过系统调用来请求获得操作系统内核的服务。
    
    程序接口由系统调用组成。
  - 系统调用与库函数的区别
    
    普通应用程序
    
    直接进行系统调用
    
    使用库函数（有的库函数会涉及系统调用）
    
    编程语言
    
    向上提供库函数
    
    或把系统调用封装为库函数
    
    操作系统
    
    向上提供系统调用
  - 小例子：为什么系统调用是必须的？
    
    用户通过系统调用请求资源，由操作系统内核进行统一管理分配，避免混乱。
  - 什么功能要用系统调用实现？
    
    系统调用（按功能分类）
    
    设备管理
    
    完成设备的请求/释放/启动等功能
    
    文件管理
    
    完成文件的读/写/创建/删除等功能
    
    进程控制
    
    完成进程的创建/撤销/阻塞/唤醒等功能
    
    进程通信
    
    完成进程之间的消息传递/信号传递等功能
    
    内存管理
    
    完成内存的分配/回收等功能
  - 系统调用的过程
    
    传递系统调用参数
    
    执行陷入/trap/访管指令（用户态）
    
    内核程序处理系统调用（核心态）
    
    返回应用程序
- 07 操作系统的体系结构
  - 内核
    
    对系统资源进行管理的功能
    
    进程管理
    
    存储器管理
    
    设备管理
    
    时钟管理
    
    利用时钟中断实现计时功能
    
    中断处理
    
    原语（设备驱动、CPU切换等）
    
    一种特殊的程序，具有原子性。这段程序的运行不能被中断。
  - 变态的过程是有成本的，消耗时间，频繁地变态会降低系统性能
  - 非内核功能
    
    如：GUI
    
    Ubuntu、CentOS主要工作是实现非内核功能，内核都是使用Linux内核
  - 大内核
    
    将操作系统的主要功能模块都作为系统内核，运行在核心态
    
    优点：高性能
    
    缺点：内核代码庞大，结构混乱，难以维护。
    
    典型的大内核/宏内核/单内核操作系统
    
    Linux、Unix
  - 微内核
    
    只把最基本的功能保留在内核
    
    优点：内核功能说好，结构清晰，方便维护
    
    缺点：需要频繁地在核心态和用户态之间切换，性能低
    
    典型的微内核操作系统
    
    Windows NT
第二章进程管理
- 01 进程的概念、组成、特征
  - 概念
    
    进程和程序的区别
    
    程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。
    
    进程（Process）：是动态的，是程序的一次执行过程。
    
    操作系统如何区分进程
    
    当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的PID（Process ID，进程ID）
  - 组成
    
    一个进程实体（进程映像）由PCB、程序段、数据段组成
    
    进程是动态的，进程实体是静态的
    
    进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
    
    PCB是进程存在的唯一标志！
    
    进程控制块（PCB）
    
    进程描述信息
    
    进程标识符PID
    
    用户标识符UID
    
    进程控制和管理信息
    
    CPU、磁盘、网络流量使用情况统计
    
    进程当前状态：就绪态/阻塞态/运行态...
    
    资源分配清单
    
    正在使用哪些文件
    
    正在使用哪些内存区域
    
    正在使用哪些I/O设备
    
    处理机相关信息
    
    PSW、PC等等各种寄存器的值（用于实现进程切换）
    
    程序段
    
    三个QQ进程的程序段相同，数据段、PCB不同
    
    数据段
  - 特征
    
    动态性（进程最基本的特征）
    
    进程是程序的一次执行过程，是动态地产生、变化和消亡的。
    
    并发性
    
    内存中有多个进程实体，各进程可并发执行
    
    独立性
    
    进程是能独立运行、独立获得资源、独立接受调度的基本单位
    
    异步性
    
    各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题。
    
    结构性
    
    每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成。
- 02 进程的状态与转换
  - 状态
    
    运行状态（Runing）
    
    占有CPU，并在CPU上运行
    
    单核CPU同一时刻只会有一个进程处于运行态，多核CPU可能有多个进程处于运行态
    
    就绪状态（Ready）
    
    具备运行条件，但由于没有空闲CPU，而暂时不能运行
    
    阻塞状态（Waiting/Blocked，又称：等待态）（三种基本状态）
    
    因等待某一事件而暂时不能运行
    
    创建状态（New，又称新建态）
    
    进程正在被创建，操作系统为进程分配资源、初始化PCB
    
    终止状态（Terminated，又称：结束态）
    
    进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB
    
    state变量，1表示创建态，2表示就绪态，3表示运行态
  - 状态间的转换
    
    就绪态➡运行态
    
    进程被调度
    
    运行态➡就绪态
    
    时间片到
    
    处理机被抢占
    
    运行态➡阻塞态
    
    等待系统资源分配
    
    或等待某时间发生（进程主动行为）
    
    阻塞态➡就绪态
    
    资源分配到位，等待的事件发生（被动行为），操作系统发起
  - 进程的组织方式
    
    链接方式
    
    按照进程状态将PCB分为多个队列
    
    操作系统持有指向各个队列的指针
    
    过程
    
    索引方式
    
    根据进程状态的不同，建立几张索引表
    
    操作系统持有指向各个索引表的指针
    
    过程
- 03 进程控制
  - 基本概念
    
    概念：进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
    
    实质：实现进程状态转换
    
    过程图
    
    如何实现进程控制：用“原语”实现
    
    如何实现原语的“原子性”
    
    用关中断指令和开中断指令这两个特权指令实现原子性
  - 进程控制相关的原语
    
    进程的创建
    
    创建原语
    
    申请空白PCB
    
    为新锦成分配所需资源
    
    初始化PCB
    
    将PCB插入就绪队列（创建态➡就绪态）
    
    引起进程创建的事件
    
    用户登录
    
    分时系统中，用户登录成功，系统会为其建立一个新的进程
    
    作业调度
    
    多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
    
    提供服务
    
    用户向操作系统提出某些请求时，会新建一个进程处理该请求
    
    应用请求
    
    由用户进程主动请求创建一个子进程
    
    进程的终止
    
    就绪态/阻塞态/运行态➡终止态➡无
    
    撤销原语
    
    从PCB集合中找到终止进程的PCB
    
    若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
    
    终止其所有子进程
    
    进程间的关系是树形结构
    
    将该进程拥有的所有资源归还给父进程或操作系统
    
    删除PCB
    
    引起进程终止的事件
    
    正常结束
    
    进程自己请求终止（exit系统调用）
    
    异常结束
    
    整数除0、非法使用特权指令，然后被操作系统强行杀掉
    
    外界干预
    
    Ctrl + Alt + delete，用户选择杀掉进程
    
    进程的阻塞
    
    阻塞原语（运行态➡阻塞态）
    
    找到要阻塞的进程对应的PCB
    
    保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
    
    将PCB插入响应时间的等待队列
    
    引起进程阻塞的事件
    
    需要等待系统分配某种资源
    
    需要等待相互合作的其他进程完成工作
    
    进程的唤醒（成对出现）
    
    唤醒原语（阻塞态➡就绪态）
    
    在事件等待队列中找到PCB
    
    将PCB从等待队列移除，设置进程为就绪态
    
    将PCB插入就绪队列，等待被调度
    
    引起进程唤醒的时间
    
    等待事件发生（因何事阻塞，就应由何事唤醒）
    
    进程的切换
    
    切换原语（运行态➡就绪态、就绪态➡运行态）
    
    将运行环境信息存入PCB
    
    PCB移入相应队列
    
    选择另一个进程执行，并更新其PCB
    
    根据PCB恢复新进程所需的运行环境
    
    引起进程切换的事件
    
    当前进程时间片到
    
    有更高优先的进程到达
    
    当前进程主动阻塞
    
    当前进程终止
- 04 进程通信
  - 进程之间的信息交换
  - 共享存储
    
    设置一个共享空间
    
    要互斥地访问共享空间
    
    两种方式
    
    基于数据结构的共享（低级）
    
    基于存储区的共享（高级）
  - 消息传递
    
    进程间的数据交换以格式化的消息（Message）为单位。
    
    进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换
    
    消息头，消息体
    
    直接通信方式
    
    消息直接挂到接收进程的消息缓冲队列上
    
    间接通信方式
    
    消息要先发送到中间实体（信箱）中，因此也称（信箱通信方式）。
    
    例子：电子邮件系统
  - 管道通信
    
    只能采用半双工通信，某一时间段内只能实现单向的传输
    
    各进程要互斥地访问管道
    
    数据以字节流写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当数据被全部取走，管道变空，读进程的read()系统调用将被阻塞。
    
    如果没写满，就不允许读。如果没读空，就不允许写。
    
    数据一旦被读出，就被抛弃，因此，读进程最多只能有一个
- 05 线程
  - 什么是线程，为什么要引入线程？
    
    线程是一个基本的CPU执行单元，也是程序执行流的最小单元。
    
    引入线程后，进程直线可以并发，进程内的各线程之间也可以并发
    
    引入线程后，进程只作为除CPU之外的系统资源的分配单位
    
    打印机、内存地址空间都是分配给进程的
  - 引入线程机制后，有什么变化
    
    资源分配、调度
    
    传统进程机制中，进程是资源分配、调度的基本单位
    
    引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
    
    并发性
    
    传统进程机制中，只能进程间并发
    
    引入线程后，各线程间也能并发，提高了并发度
    
    系统开销
    
    传统的进程间并发，需要切换进程的运行环境，系统开销很大
    
    线程间并发，如果是统一进程内的线程切换，不需要切换进程环境，开销小
    
    引入线程后，并发所带来的系统开销减小
  - 线程有哪些重要的属性
    
    线程是处理机调度的单位
    
    多CPU计算机中，各个线程可占用不同的CPU
    
    每个线程都有一个线程id，线程控制块（TCB）
    
    线程也有就绪、阻塞、运行三种基本状态
    
    线程几乎不用有系统资源
    
    同一进程的不同线程间共享进程的资源
    
    由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
    
    同一进程中的线程切换，不会引起进程切换
    
    不同进程中的线程切换，会引起进程切换
    
    切换同进程内的线程，系统开销很小
    
    切换进程，系统开销较大
- 06 线程的实现方式——多线程模型
  - 线程实现的方式
    
    用户级线程（User-Level-thread，ULT）
    
    线程库
    
    优点
    
    开销小，效率高
    
    缺点
    
    如果单个线程被阻塞，整个进程都会被阻塞，并发度不高。
    
    多个线程无法在多核处理机上并行运行。
    
    内核级线程
    
    操作系统会为每个内核级线程建立相应的TCB (Thread Control Block，线程控制块)，通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”
    
    优点
    
    当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。
    
    多线程可在多核处理机上并行执行。
    
    缺点
    
    一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
  - 多线程模型
    
    一对一模型
    
    一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
    
    优点
    
    当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。
    
    多线程可在多核处理机上并行执行。
    
    缺点
    
    一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
    
    多对一模型
    
    多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。
    
    优点
    
    用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
    
    缺点
    
    当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度低。多个线程不可在多核处理机上并行运行
    
    操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。
    
    多对多模型
    
    n用户及线程映射到m个内核级线程(n>=m)。每个用户进程对应m个内核级线程。
    
    克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。
    
    用户级线程是“代码逻辑”的载体
    
    内核级线程是“运行机会”的载体
- 07 处理机调度概念、层次
  - 处理机调度
    
    基本概念
    
    当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。
    
    三个层次
    
    高级调度（作业调度）
    
    按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程，每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撒销PCB。
    
    中级调度（内存调度）
    
    按照某种策略决定将哪个处于挂起状态的进程重新调入内存。
    
    内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。
    
    暂时调到外存等待的进程状态为挂起状态（挂起态，suspend）。被挂起的进程PCB会被组织成挂起队列
    
    高频
    
    低级调度（进程调度/处理机调度）
    
    按照某种策略从就绪队列中选取一一个进程，将处理机分配给它。
    
    进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
    
    三层调度的联系、对比
    
    补充知识
    
    进程的“挂起态”
    
    就绪挂起
    
    阻塞挂起
    
    七状态模型
- 08 进程调度的时机、切换与过程调度方式
  - 时机
    
    什么时候需要进程调度?
    
    主动放弃
    
    进程正常终止
    
    运行过程中发生异常而终止
    
    进程主动请求阻塞（如等待I/O）
    
    被动放弃
    
    分给进程的时间片用完
    
    有更紧急的事需要处理（如I/O中断）
    
    有更高优先级的进程进入就绪队列
    
    什么时候不能进行进程调度?
    
    在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
    
    进程在操作系统内核程序临界区中。
    
    在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列）
    
    2012年联考真题
    
    进程在操作系统内核程序临界区中不能进行调度与切换✅
    
    进程处于临界区时不能进行处理机调度❌
    
    普通临界区/内核临界区
    
    临界资源
    
    一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
    
    临界区
    
    访问临界资源的那段代码。
    
    内核程序临界区
    
    一般是用来访问某种内核数据结构的
    
    如：进程的就绪队列(由各就绪进程的PCB组成)
  - 切换与过程
    
    "狭义的调度"与"切换”的区别
    
    狭义的进程调度
    
    指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换)
    
    进程切换
    
    指一个进程让出处理机，由另一个进程占用处理机的过程。
    
    广义的进程调度包含了选择一个进程和进程切换两个步骤。
    
    进程切换的过程需要做什么?
    
    过程
    
    对原来运行进程各种数据的保存
    
    对新的进程各种数据的恢复(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)
    
    有代价的，如果过于频繁进行进程调度、切换，系统的效率会降低。
  - 方式
    
    非剥夺调度方式(非抢占式)
    
    非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
    
    实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
    
    剥夺调度方式(抢占式)
    
    剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
    
    可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能( 通过时钟中断)。适合于分时操作系统、实时操作系统
- 09 调度算法的评价指标（计算）
  - CPU利用率
    
    指CPU“忙碌”的时间占总时间的比例。
    
    利用率 = 忙碌的时间/总时间（道/秒）
    
    甘特图
  - 系统吞吐量
    
    单位时间内完成作业的数量
    
    系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间
  - 周转时间
    
    周转时间
    
    指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
    
    （作业）周转时间 = 作业完成时间 - 作业提交时间
    
    四部分
    
    作业在外存后备队列上等待作业调度(高级调度)的时间
    
    进程在就绪队列上等待进程调度( 低级调度)的时间
    
    进程在CPU上执行的时间
    
    进程等待I/O操作完成的时间
    
    后三项在一个作业的整个处理过程中，可能发生多次。
    
    平均周转时间
    
    平均周转时间 = 各作业周转时间之和 / 作业数
    
    带权周转时间
    
    带权周转时间 = 作业周转时间 / 作业实际运行的时间
    
    平均带权周转时间
    
    平均带权周转时间 = 各作业带权周转时间之和 / 作业数
  - 等待时间
    
    指进程/作业处于等待处理机状态时间之和。
    
    对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。
    
    对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
    
    调度算法只会影响作业/进程的等待时间。
    
    平均等待时间即各个进程/作业等待时间的平均值
  - 响应时间
    
    指从用户提交请求到首次产生响应所用的时间。
- 10 调度算法先来先服务、最短作业优先、最高响应比优先
  - 先来先服务（FCFS，First Come First Serve）
    
    算法规则
    
    按照作业/进程到达的先后顺序进行服务
    
    用于作业/进程调度
    
    用于作业调度时，考虑的是哪个作业先到达后备队列
    
    用于进程调度时，考虑的是哪个进程先到达就绪队列
    
    非抢占式
    
    优点
    
    公平、算法实现简单
    
    缺点
    
    排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利
    
    例如：排队买奶茶
  - 最短作业优先（SJF）
    
    思想
    
    追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间
    
    算法规则
    
    最短的作业/进程优先得到服务(所谓“最短”，是指要求服务时间最短)
    
    每次调度时选择当前已到达且运行时间最短的作业/进程
    
    用于作业/进程调度
    
    即可用于作业调度，也可用于进程调度。
    
    用于进程调度时称为“短进程优先(SPF, Shortest Process First)算法
    
    非抢占式
    
    SJF和SPF是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法( SRTN, Shortest Remaining Time Next )
    
    最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。
    
    细节
    
    如果未特别说明，短作业/进程优先算法默认是非抢占式的
    
    在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少
    
    抢占式的短作业/进程优先调度算法(最短剩余时间优先, SRNT算法)的平均等待时间、平均周转时间最少”
    
    缺点
    
    对短作业有利，长作业不利。
    
    可能产生饥饿现象。
  - 最高响应比优先（HRRN，Highest Reponse Ratio Next）
    
    思想
    
    要综合考虑作业/进程的等待时间和要求服务的时间
    
    算法规则
    
    在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
    
    响应比 = （等待时间 + 要求服务时间）/ 要求服务时间
    
    用于作业/进程调度
    
    既可用于作业调度，也可用于进程调度
    
    是否可抢占
    
    非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
    
    优缺点
    
    综合考虑了等待时间和运行时间(要求服务时间)等待时间相同时，要求服务时间短的优先(SJF 的优点)要求服务时间相同时，等待时间长的优先(FCFS 的优点)对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
    
    是否饥饿
    
    不会导致饥饿
  - 三种算法的比较
  - 适用性
    
    适用于早起的批处理系统，FCFS算法也常结合其他的算法使用
- 11 调度算法——时间片轮转、优先级调度、多级反馈队列
  - 时间片轮转调度算法（RR，Round-Robin）
    
    算法规则
    
    按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
    
    用于作业/进程调度
    
    用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)
    
    是否可抢占
    
    若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。
    
    由时钟装置发出时钟中断来通知CPU时间片已到。
    
    优缺点
    
    优点
    
    公平；响应快，适用于分时操作系统。
    
    缺点
    
    由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
    
    不会饥饿
    
    时间片过大的影响
    
    如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
  - 优先级调度算法
    
    算法思想
    
    随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序。
    
    调度规则
    
    调度时选择优先级最高的作业/进程
    
    用于作业调度/进程调度
    
    既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中
    
    是否可抢占
    
    抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
    
    优缺点
    
    优点
    
    用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
    
    缺点
    
    若源源不断地有高优先级进程到来，则可能导致饥
    
    会导致饥饿
  - 多级反馈队列调度算法
    
    算法思想
    
    对其他调度算法的折中权衡
    
    算法规则
    
    设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    
    新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾
    
    只有第k级队列为空时，才会为k+1级队头的进程分配时间片
    
    抢占式
    
    在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
    
    优点
    
    对各类型进程相对公平(FCFS的优点) ；
    
    每个新到达的进程都可以很快就得到响应(RR的优点)；
    
    短进程只用较少的时间就可完成(SPF的优点) ；
    
    不必实现估计进程的运行时间(避免用户作假) ;
    
    可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/0密集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级)
    
    会饥饿
  - 综合比较
  - 适合于交互式系统，比如：Unix
- 12 进程同步、进程互斥
  - 进程同步
    
    并发性带来了异步性，有时需要通过进程同步解决这种异步问题。
    
    有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循- -定的先后顺序。
  - 进程互斥
    
    对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源
    
    四个部分
    
    进入区
    
    检查是否可进入临界区，若可进入，需要“上锁”
    
    临界区
    
    访问临界资源的那段代码
    
    退出区
    
    负责"解锁"
    
    剩余区
    
    其余代码部分
    
    需要遵循的原则
    
    空闲让进
    
    临界区空闲时，应允许一个进程访问
    
    忙则等待
    
    日临界区正在被访问时，其他试图访问的进程需要等待
    
    有限等待
    
    要在有限时间内进入临界区，保证不会饥饿
    
    让权等待
    
    日进不了临界区的进程，要释放处理机，防止忙等
- 13 进程互斥的软件实现方法
  - 单标志法
    
    算法思想
    
    两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
    
    int turn = 0; //turn表示当前允许进入临界区的进程号
    
    同一时刻最多只允许一个进程访问临界区
  - 双标志先检查
    
    算法思想
    
    设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = ture” 意味着0号进程PO现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[]设为true,之后开始访问临界区。
  - 双标志后检查
    
    算法思想
    
    双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。
    
    优劣
    
    解决了“忙则等待”的问题，违背了“空闲让进”和“有限等待”原则，会产生饥饿。
  - Peterson算法
    
    算法思想
    
    结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”(谦让)。做一个有礼貌的进程。
    
    bool flag[2]; // 表示进入临界区意愿的数组，初始值都是false
    
    int turn = 0; // turn表示优先让哪个进程进入临界区
    
    图解
    
    优劣
    
    用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。
- 14 进程互斥的硬件实现方法
  - 中断屏蔽方法
    
    使用“开关中断”指令实现
    
    优点
    
    简单高效
    
    缺点
    
    只适用于单处理机
    
    只适用于操作系统内核进程
  - TestAndSet（TS指令/TSL指令）
    
    过程：
    
    old记录是否被上锁
    
    再将lock设为true
    
    检查临界区是否已被上锁（若已上锁，则循环重复前几步）
    
    优点
    
    实现简单
    
    适用于多处理机环境
    
    缺点
    
    不满足“让权等待”
  - Swap指令（XCHG指令）
    
    同TSL
- 15 信号量机制
  - 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
    
    信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。
    
    原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
    
    一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。
    
    wait、signal 原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)
  - 整型信号量
    
    用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
    
    整型信号量与普通整型变量的区别:对信号量只能执行初始化、P、V三种操作
    
    存在的问题
    
    不满足“让权等待”原则，会发生“忙等”
  - 记录型信号量（高频考点）
    
    即用记录型数据结构表示的信号量。
    
    S.value表示某种资源数, S.L 指向等待该资源的队列
    
    P 操作中，一定是先S.value--，之后可能需要执行block原语
    
    V 操作中，一定是先S.value++,之后可能需要执行wakeup原语
    
    注意
    
    要能够自己推断在什么条件下需要执行block或wakeup
    
    功能
    
    可以用记录型信号量实现系统资源的"申请"和"释放"
    
    可以用记录型信号量实现进程互斥、进程同步
    
    过程
- 16 用信号量机制实现进程互斥、同步、前驱关系
  - 一个信号量对应一种资源
  - 实现进程互斥
    
    过程
    
    分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应该放在临界区）
    
    设置互斥信号量mutex，初值为1（semaphore mutex = 1; // 初始化信号量，默认是记录型信号量）
    
    在进入区P(mutex)——申请资源
    
    在退出区V(mutex)——释放资源
    
    注意：
    
    对不同的临界资源需要设置不同的互斥信号量。
    
    P、V操作必须成对出现。
  - 实现进程同步
    
    过程
    
    1.分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
    
    2.设置同步信号量S，初始为0
    
    3. 在“前操作”之后执行V(S)
    
    4.在“后操作”之前执行P(S)
    
    前V后P
    
    演示
  - 实现进程的前驱关系
    
    过程
    
    要为每一对前驱关系各设置一个同步信号量
    
    在“前操作”之后对相应的同步信号量执行V操作
    
    在“后操作”之前对相应的同步信号量执行P操作
    
    实现进程的前驱关系
- 17 生产者消费者问题
  - 如何实现
    
    生产者、消费者共享一个初始为空、大小为n的缓冲区。
    
    只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
    
    只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
    
    缓冲区是临界资源，各进程必须互斥地访问。
    
    实现图解
  - 思考：能否改变相邻P、V操作的顺序？
    
    会发生死锁
    
    实现互斥的P操作一定要在实现同步的P操作之后
    
    V操作不会导致进程阻塞，因此，两个V操作顺序可以交换
  - 易错点
    
    实现互斥和实现同步的两个P操作的先后顺序（死锁问题）
  - 两对同步关系
- 18 多生产者-多消费者
  - 加上互斥信号量。互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”
  - 解题思路
    
    1.关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
    
    2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
    
    3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。 (互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少)
  - 解决“多生产者-多消费者问题”的关键在于理清复杂的同步关系。
    
    在分析同步问题(一前一后问题)的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系。
  - 过程关系
- 19 吸烟者问题
  - 代码分析
- 20 读者-写者问题
  - 实现
  - 两种问题的区别与使用
- 21 哲学家进餐问题
  - 每个进程需要同时持有多个临界资源
  - 防止死锁的发生
    
    方案①、②
    
    方案③
- 22 管程
  - 为什么要引入管程
    
    信号量机制存在的问题
    
    编写程序困难、易出错
    
    高级同步机制
    
    封装的思想
  - 定义
    
    管程是一种特殊的软件模块
  - 组成部分
    
    1. 局部于管程的共享数据结构说明；
    
    2. 对该数据结构进行操作的一组过程；
    
    3. 对局部于管程的共享数据设置初始值的语句；
    
    4. 管程有一个名字。
  - 基本特征
    
    1. 局部于管程的数据只能被局部于管程的过程所访问;
    
    2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
    
    3. 每次仅允许一个进程在管程内执行某个内部过程。
  - 拓展1：用管程解决生产者消费者问题
    
    各进程必须互斥访问管程的特性是由编译器实现的
    
    实现方法
    
    具体过程
    
    1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
    
    2. 需要在管程中定义用于访问这些共享数据的“入口”——其实就是一-些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
    
    3. 只有通过这些特定的“入口”才能访问共享数据
    
    4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的，程序员不用关心) 。
    
    5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出“入口”) ；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
    
    程序员可以用某种特殊的语法来定义一个管程monitor，之后其他程序员可以使用这个管程提供的入口，方便实现进程同步/互斥
  - 拓展2：Java中类似于管程的机制
    
    Java中的synchronized
- 23 死锁的概念
  - 什么是死锁
    
    在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。
    
    发生死锁后若无外力干涉，这些进程都将无法向前推进。
  - 进程死锁、饥饿、死循环的区别
    
    死锁
    
    各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
    
    饥饿
    
    由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先(SPF) 算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。
    
    死循环
    
    某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。
    
    三者的区别
  - 死锁产生的必要条件
    
    互斥条件
    
    只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。
    
    不剥夺条件
    
    进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
    
    请求和保持条件
    
    进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
    
    循环等待条件
    
    存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
    
    发生死锁时一定有循环等待，但是发生循环等待时未必死锁
  - 什么时候会发生死锁
    
    对不可剥夺资源的不合理分配，可能导致死锁
    
    1. 对系统资源的竞争。各进程对不可剥夺的资源( 如打印机)的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的。.
    
    2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1,两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
    
    3.信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。( 可以把互斥信号量、同步信号量也看做是一"种抽象的系统资源)
  - 死锁的处理逻辑
    
    预防死锁
    
    破坏死锁产生的四个必要条件
    
    避免死锁
    
    避免系统进入不安全状态（银行家算法）
    
    死锁的检测和解除
    
    允许死锁发生，系统负责检测出死锁并解除
- 24 死锁的处理策略——预防死锁（静态策略）
  - 破坏互斥条件
    
    只有对必须互斥使用的资源的争抢才会导致死锁。
    
    SPOOLing技术把独占设备在逻辑上改造成共享设备
  - 破坏不剥夺条件
    
    不剥夺条件：
    
    进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
    
    方案一
    
    某些资源上位使用完，也要主动释放，从而破坏不可剥夺条件。
    
    方案二
    
    当某个进程需要的资源被其他进程所占有的时候，由操作系统协助，将想要的资源强行剥夺。
    
    缺点
    
    实现复杂
    
    可能会造成前一阶段工作的失效。只适用于易保存和恢复状态的资源，如CPU
    
    增加系统开销，降低系统吞吐量
    
    可能导致某个进程饥饿
  - 破坏请求和保持条件
    
    请求和保持条件：
    
    进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
    
    采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
    
    缺点
    
    资源利用率低。导致某些进程饥饿。
  - 破坏循环等待条件
    
    循环等待条件
    
    存在一种进程资源的循环等待链，链中的每一- 个进程已获得的资源同时被下一一个进程所请求。
    
    可采用顺序资源分配法。
    
    首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源(即编号相同的资源)一次申请完。
    
    原理分析
    
    一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。
    
    缺点
    
    不方便增加新设备
    
    会导致资源浪费
    
    用户变成麻烦
- 25 死锁的处理策略——避免死锁（动态策略）
  - 什么是安全序列
    
    如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要找出一个安全序列，系统就是安全状态，安全序列可能有多个。
  - 什么是系统的不安全状态，与死锁有何联系
    
    如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。可能会导致所有进程都无法顺利的执行下去，也有可能冲洗你回到安全状态。
    
    如果处于安全状态，就一定不会发生死锁。如果进入不安全状态，可能会导致死锁。
  - 如何避免系统进入不安全状态——银行家算法
    
    数据结构
    
    长度为m的一-维数组Available 表示还有多少可用资源
    
    n*m矩阵Max表示各进程对资源的最大需求数
    
    n*m矩阵Allocation表示已经给各进程分配了多少资源
    
    Max-Allocation=Need矩阵表示各进程最多还需要多少资源
    
    用长度为m的一-位数组Request表示进程此次申请的各种资源数
    
    银行家算法步骤
    
    ①检查此次申请是否超过了之前声明的最大需求数
    
    ②检查此时系统剩余的可用资源是否还能满足这次请求
    
    ③试探着分配，更改各数据结构
    
    ④用安全性算法检查此次分配是否会导致系统进入不安全状态
    
    安全性算法步骤
    
    检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列,并把该进程持有的资源全部回收。
    
    不断重复上述过程，看最终是否能让所有进程都加入安全序列。
  - 系统处于不安全状态未必死锁，但死锁时一定处于不安全状态。系统处于安全状态一定不会死锁。
- 26 死锁的处理策略——检测和解除（允许死锁的发生）
  - 死锁的检测
    
    数据结构资源分配图
    
    两种结点
    
    进程结点
    
    对应一个进程
    
    资源结点
    
    对应一类资源，一类资源可能有多个
    
    两种边
    
    进程结点——>资源结点
    
    表示进程想申请几个资源（每条边代表一个）
    
    资源结点——>进程结点
    
    表示已经为进程分配了几个资源（每条边代表一个）
    
    是否可以消除所有边
    
    检测死锁的算法
    
    1)在资源分配图中，找出既不阻塞又不是孤点的进程Pi (即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源)。消去它所有的请求边和分配边，使之称为孤立的结点。在下图中，P1是满足这一条件的进程结点，于是将P1的所有边消去。
    
    2)进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2就满足这样的条件。根据1)中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。
    
    死锁定理
    
    如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。
  - 死锁的解除
    
    一旦检测出死锁的发生，就应该立即解除死锁
    
    并不是系统中所有的进程都是死锁状态。用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程
    
    解除死锁的主要方法有
    
    1. 资源剥夺法。挂起( 暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
    
    2. 撤销进程法(或称终止进程法)。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
    
    3. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。
    
    如何决定“对谁动手”
    
    1.进程优先级
    
    2.已执行多长时间
    
    3.还要多久能完成
    
    4.进程已经使用了多少资源
    
    5.进程是交互式的还是批处理式的
第三章内存管理
- 01 内存的基础知识
  - 什么是内存，有何作用
    
    内存可存放数据。
    
    程序执行前需要先放到内存中才能被CPU处理——缓冲CPU与硬盘之间的速度矛盾
    
    按字节编址
    
    每个存储单元大小为1字节
    
    按字编址
    
    如果字长为16位，按字编址，每个存储单元大小为1个字；16个二进制位
  - 进程运行的基本原理
    
    指令的工作原理
    
    操作码+参数
    
    MOV, A, B
    
    逻辑地址VS物理地址
    
    相对地址
    
    绝对地址
    
    如何实现地址转换
    
    装入的三种方式
    
    绝对装入
    
    编译时产生绝对地址
    
    可重定位装入（静态重定位）
    
    一次分配完所需要的内存空间
    
    动态运行时装入（动态重定位）
    
    动态重定位
    
    重定位寄存器
    
    从写程序到程序运行的过程
    
    编译
    
    由编译程序将用户源代码编译成若千个目标模块(编译就是把高级语言翻译为机器语言)
    
    链接
    
    由链接程序将编译后形成的一-组目标模块，以及所需库函数链接在一起，形成-一个完整的装入模块
    
    装入(装载)
    
    由装入程序将装入模块装入内存运行
    
    链接的三种方式
    
    静态链接
    
    在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件(装入模块) ，之后不再拆开。
    
    装入时动态链接
    
    将各目标模块装入内存时，边装入边链接的链接方式。
    
    运行时动态链接
    
    在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。
- 02 内存管理的概念
  - 内存空间的分配与回收
  - 内存空间的扩充
  - 地址转换
    
    逻辑地址与物理地址的转换
    
    三种装入方式
    
    绝对装入（单道程序阶段，无操作系统）
    
    编译时产生绝对地址
    
    可重定位装入（早期多道批处理阶段）
    
    装入时将逻辑地址转换为物理地址
    
    动态运行时装入（现代操作系统）
    
    运行时将逻辑地址转换为物理地址，需设置重定位寄存器
  - 存储保护
    
    保证各进程在自己的内存空间内运行，不会越界访问
    
    两种方式
    
    设置上下限寄存器
    
    利用重定位寄存器、界地址寄存器进行判断
- 03 覆盖与交换（内存空间的扩充）
  - 覆盖技术
    
    解决程序大小超过物理内存总和
    
    将程序分段
    
    固定区
    
    调入后就不再调出，直至运行结束
    
    覆盖区
    
    覆盖区中的程序段在运行过程中会根据需要调入调出
    
    必须由程序员声明覆盖结构，操作系统完成自动覆盖。
    
    缺点
    
    对用户不透明，增加了用户编程负担
  - 交换（对换）技术
    
    内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)
    
    中级调度（内存调度）
    
    决定将哪个处于挂起状态的进程重新调入内存
    
    在外存的什么位置保存被换出的进程
    
    具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。
    
    文件区
    
    主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式。
    
    对换区
    
    对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式( 学过文件管理章节后即可理解)。总之，对换区的I/O速度比文件区的更快。
    
    什么时候交换
    
    内存吃紧时进行，系统负荷降低就暂停
    
    例如
    
    在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程:
    
    如果缺页率明显下降，就可以暂停换出。
    
    应该换出哪些进程
    
    优先换出阻塞进程
    
    可换出优先级低的进程
    
    防止优先级低的进程在被调入内存后很快被换出，还需考虑进程在内存的驻留时间
    
    PCB会常驻内存
  - 虚拟存储技术
- 04 连续分配管理方式
  - 单一连续分配
    
    内存被分为系统区、用户区
    
    内存中只能有一道用户程序，用户程序独占整个用户区
    
    优点
    
    实现简单
    
    无外部碎片
    
    可以采用覆盖技术扩充内存
    
    不一定需要采取内存保护
    
    缺点
    
    只能用于单用户、单任务操作系统
    
    有内部碎片（有些内部空间没有被利用到）
    
    存储利用率极低
  - 固定分区分配
    
    分区大小相等
    
    缺乏灵活性，适用于一台计算机控制多个相同对象的场合
    
    分区大小不等
    
    增加了灵活性，满足不同大小的进程需求，操作系统根据作业大小情况进行划分
    
    无外部碎片，有内部碎片
  - 动态分区分配
    
    根据进程大小动态地建立分区
    
    分区的大小和数目是可变的
    
    采用什么数据结构记录内存的使用情况
    
    空闲分区表
    
    空闲分区链
    
    动态分区分配算法
    
    动态分区分配没有内部碎片，但是有外部碎片
    
    内部碎片，分配给某进程的内存区域中，有些部分没有用上
    
    外部碎片，内存中的某些空闲分区由于太小而难以利用
    
    外部碎片可用“紧凑”技术来解决
    
    回收内存的四种情况
    
    回收区之后有相邻的空闲分区
    
    回收区之前有相邻的空闲分区
    
    回收区前、后都有相邻的空闲分区
    
    回收区前、后都没有相邻的空闲分区
- 05 动态分区分配算法
  - 首次适应算法（FF，First Fit）
    
    算法思想
    
    每次都从低地址开始查找，找到第一- 个能满足大小的空闲分区。
    
    如何实现
    
    空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
  - 最佳适应算法（BF，Best Fit）
    
    算法思想
    
    由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区即，优先使用更小的空闲区。
    
    如何实现
    
    空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链( 或空闲分区表)，找到大小能满足要求的第一个空闲分区。
    
    缺点
    
    每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。
  - 最坏适应算法（WF，Worst Fit）
    
    又称最大适应算法（Largest Fit）
    
    算法思想
    
    为了解决最佳适应算法的问题一---即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
    
    如何实现
    
    空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
  - 邻近适应算法（NF，Next Fit）
    
    算法思想
    
    首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
    
    如何实现
    
    空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
    
    优点
    
    首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)
    
    邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用(最大适应算法的缺点)
    
    首次适应算法效果最好
  - 比较
- 06 基本分页存储管理的基本概念
  - 内存空间的分配与回收
    
    连续分配管理方式
    
    连续分配：为用户进程分配的必须是一一个连续的内存空间。
    
    非连续分配管理方式
    
    非连续分配：为用户进程分配的可以是-一些分散的内存空间。
    
    基本分页存储管理
    
    什么是分页存储
    
    内存空间分为一个个大小相等的分区，每个分区就是一个“页框”（页框=页帧=内存块=物理块=物理页面）。每个页框有一个编号，即“页框号”（页框号=页帧号=内存块号=物理块号=物理页号），页框号从0开始。
    
    将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始
    
    进程的页面与内存的页框有一一对应的关系。
    
    各个页面不必连续存放，可以放到不相邻的各个页框中。
    
    易混淆
    
    页、页面 vs 页框、页帧、物理页；
    
    页号、页面号 vs 页框号、页帧号、物理页号
    
    页表
    
    页表通常存在PCB中
    
    一个进程对应一张页表
    
    进程的每个页面对应一个页表项
    
    每个页表项由“页号”和“块号”组成
    
    页表记录进程页面和实际存放的内存块之间的映射关系
    
    具体关系图
    
    已知内存大小，页面大小，计算每个页表项需要多大
    
    内存大小/页面大小，换算为比特位，再转换为字节
    
    计算方法
    
    如何实现地址转换
    
    1. 计算出逻辑地址对应的【页号，业内偏移量】
    
    2. 找到对应页面在内存中的存放位置（查页表）
    
    3. 物理地址 = 页面始址 + 页内偏移量
    
    逻辑地质结构——可拆分为【页号P，页内偏移量W】
    
    页号 = 逻辑地址 / 页面大小；
    
    页内偏移量 = 逻辑地址 % 页面大小
    
    如果页面大小刚好是2的整数次幂呢
    
    结论:如果每个页面大小为2^K B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分就是页号
    
    基本地址变换机构【见P7】
    
    基本分段存储管理
    
    段页式存储管理
  - 内存空间的扩充
  - 地址转换
  - 存储保护
- 07 基本地址变换机构
  - 页表寄存器的作用
    
    存放页表起始地址
    
    存放页表长度
  - ⚡地址变换过程
    
    1. 根据逻辑地址算出页号、页内偏移量
    
    2. 页号的合法性检查(与页表长度对比)
    
    3. 若页号合法，再根据页表起始地址、页号找到对应页表项
    
    4. 根据页表项中记录的内存块号、页内偏移量得到最终的物理地址
    
    5. 访问物理内存对应的内存单元
  - 其他小细节
    
    页内偏移量位数与页面大小之间的关系(要能用其中一个条件推出另一个条件)
    
    页式管理中地址是一维的
    
    实际应用中，通常使-个页框恰好能放入整数个页表项
    
    为了方便找到页表项，页表- -般是放在连续的内存块中的
- 08 具有快表的地址变换机构
  - 什么是快表（TLB）
    
    快表，又称联想寄存器(TLB， translation lookaside buffer)，是一种访问速度比内存快很多的高速缓存(TLB不是内存! )，用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。
  - 引入快表后，地址的变换过程
    
    ①CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
    
    ②如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
    
    ③如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存(注意:在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一-定的算法对旧的页表项进行替换)
  - 局部性原理
    
    时间局部性
    
    如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。( 因为程序中存在大量的循环)
    
    空间局部性
    
    一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)
  - 对比图
- 09 两级页表
  - 单级页表存在什么问题?如何解决?
    
    所有页表项必须连续存放，页表过大时需要很大的连续空间
    
    在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存
  - 两级页表
    
    将长长的页表再分页
    
    逻辑地址结构: 【一级页号，二级页号，页内偏移量】
    
    注意几个术语:页目录表/外层页表/顶级页表
  - 如何实现地址变换?
    
    ①按照地址结构将逻辑地址拆分成三部分
    
    ②从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
    
    ③根据二级页号查表，找到最终想访问的内存块号
    
    ④结合页内偏移量得到物理地址
  - 两级页表问题需要注意的几个细节
    
    多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级
    
    多级页表的访存次数(假设没有快表机构) ——N 级页表访问一个逻辑地址需要N+ 1次访存
- 10 基本分段存储管理方式
  - 什么是分段(类似于分页管理中的"分页")
    
    将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址
    
    每个段在内存中占据连续空间，但各段之间可以不相邻
    
    逻辑地址结构：【段号，段内地址】
  - 什么是段表(类似于分页管理中的"页表")
    
    记录逻辑段到实际存储地址的映射关系
    
    每个段对应-个段表项。各段表项长度相同，由段号(隐含)段长、基址组成
  - 如何实现地址变换
    
    1. 由逻辑地址得到段号、段内地址
    
    2. 段号与段表寄存器中的段长度比较，检查是否越界
    
    3. 由段表始址、段号找到对应段表项
    
    4. 根据段表中记录的段长，检查段内地址是否越界
    
    5. 由段表中的“基址+段内地址”得到最终的物理地址
    
    6. 访问目标单元
  - 分段、分页管理的对比
    
    分页对用户不可见，分段对用户可见
    
    分页的地址空间是一维的，分段的地址空间是二维的
    
    分段更容易实现信息的共享和保护(纯代码可重入代码可以共享)
    
    分页(单级页表)、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构
- 11 段页式管理方式
  - 分页、分段管理方式中最大的优缺点
    
    将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面
    
    将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
    
    逻辑地址结构:【段号，页号，页内偏移量】
  - 分段 + 分页的结合——段页式管理方式
    
    每个段对应一个段表项。各段表项长度相同，由段号(隐含)、页表长度、页表存放地址组成
    
    每个页对应一个页表项。各页表项长度相同，由页号(隐含)、页面存放的内存块号组成
  - 段表、页表
    
    1. 由逻辑地址得到段号、页号、页内偏移量
    
    2. 段号与段表寄存器中的段长度比较，检查是否越界
    
    3. 由段表始址、段号找到对应段表项
    
    4. 根据段表中记录的页表长度，检查页号是否越界
    
    5. 由段表中的页表地址、页号得到查询页表，找到相应页表项
    
    6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
    
    7. 访问目标单元
  - 如何实现地址变换
    
    第一次——查段表、第二次——查页表、第三次——访问目标单元
    
    可引入快表机构，以段号和页号为关键字查询快表，即可直接找到
    
    最终的目标页面存放位置。引入快表后仅需-次访存
- 12 虚拟内存的基本概念
  - 传统存储管理方式的特征、缺点
    
    一次性
    
    作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：
    
    ①作业很大时，不能全部装入内存，导致大作业无法运行；
    
    ②当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
    
    驻留性
    
    一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。
  - 局部性原理
    
    时间局部性
    
    现在访问的指令、数据在不久后很可能会被再次访问
    
    空间局部性
    
    现在访问的内存单元周围的内存空间，很可能在不久后会被访问
    
    高速缓存技术
    
    使用频繁的数据放到更高速的存储器中
  - 虚拟内存的定义和特征
    
    定义
    
    程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据。
    
    多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
    
    对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
    
    虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
  - 如何实现虚拟内存技术
    
    借助离散分配的内存管理方式（基本分页存储管理、基本分段、基本段页式）
    
    访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(请求调页功能)
    
    内存空间不够时，将内存中暂时用不到的信息换出到外存(页面置换功能)
    
    虚拟内存的实现
    
    请求分页存储管理
    
    请求调页
    
    页面置换
    
    请求分段存储管理
    
    请求调段
    
    段置换
    
    请求段页式存储管理
- 13 请求分页管理方式
  - 页表机制
    
    在基本分页的基础上增加了几个表项
    
    状态位：表示页面是否已在内存中
    
    访问字段：记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
    
    修改位：表示页面调入内存后是否被修改过，只有修改过的页面才需在置换时写回外存
    
    外存地址：页面在外存中存放的位置
  - 缺页中断机构
    
    找到页表项后检查页面是否已在内存，若没在内存,产生缺页中断
    
    缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面
    
    缺页中断属于内中断，属于内中断中的“故障"，即可能被系统修复的异常
    
    一条指令在执行过程中可能产生多次缺页中断
  - 地址变换机构
    
    找到页表项是需要检查页面是否在内存中
    
    若页面不再内存中，需要请求调页
    
    若内存空间不够，还需换出页面
    
    页面调入内存后，需要修改相应页表项
- 14 页面置换算法
  - 最佳置换算法(OPT)
    
    最佳置换算法(OPT, Optimal) :每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
    
    最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。
  - 先进先出置换算法(FIFO)
    
    先进先出置换算法(FIFO) ：每次选择淘汰的页面是最早进入内存的页面
    
    实现方法:把调入内存的页面根据调入的先后顺序排成一一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
    
    Belady异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
    
    只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差
  - 最近最久未使用置换算法(LRU)
    
    最近最久未使用置换算法(LRU， least recently used)：每次淘汰的页面是最近最久未使用的页面
    
    实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。
    
    当需要淘汰：一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。
  - 时钟置换算法(CLOCK)
    
    时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，Not Recently Used)
    
    简单的CLOCK算法实现方法：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。
    
    当某页被访问时，其访问位置为1。
    
    当需要淘汰一个页面时，只需检查页的访问位。
    
    如果是0，就选择该页换出；
    
    如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)
  - 改进型的时钟置换算法
    
    简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/0操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
    
    因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。
    
    为方便讨论，用(访问位，修改位)的形式表示各页面状态。如(1，1)表示一个页面近期被访问过,且被修改过。
    
    算法规则
  - 几种置换算法的比较
- 15 页面分配策略
  - 驻留集
    
    驻留集
    
    指请求分页存储管理中给进程分配的物理块的集合。
    
    在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
    
    若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少；
    
    驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。
    
    固定分配：操作系统为每个进程分配- -组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
    
    可变分配：先为每个进程分配--定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变
    
    局部置换：发生缺页时只能选进程自己的物理块进行置换。
    
    全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
  - 页面分配、置换策略
    
    固定分配局部置换
    
    固定分配局部置换:系统为每个进程分配-一定数量的物理英,”在整个运行期向都不改变。若进程在运外行中发生缺页，则只能从该进程在内存中的页面中选出一- 页换出，然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为- - 个进程分配的内存块数)
    
    可变分配全局置换
    
    刚开始会为每个进程分配一定数量的物理块。操作系统会保持- - 个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程;若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，.都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
    
    可变分配局部置换
    
    刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
    
    区别
    
    可变分配全局置换：只要缺页就给分配新物理块
    
    可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块
  - 调入页面的时机
    
    预调页策略：一般用于进程运行前
    
    请求调页策略：进程运行时，发现缺页再调页
  - 从何处调页
    
    对换区——采用连续存储方式，速度更快；文件区——采用离散存储方式，速度更慢。
    
    对换区足够大：运行将数据从文件区复制到对换区，之后所有的页面调入、调出都是在内存与对换区之间进行
    
    对换区不够大：不会修改的数据每次都从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
  - 抖动(颠簸)现象
    
    页面频繁换入换出的现象。主要原因是分配给进程的物理块不够
  - 工作集
    
    在某段时间间隔里，进程实际访问页面的集合。驻留集大小一般不能小于工作集大小。
第四章文件管理
- 01 初识文件管理
  - 文件定义：一组有意义的信息的集合
  - 文件的属性
    
    文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
    
    标识符：一个系统内的各文件标识符唯-一，对用户来说毫无可读性,因此标识符只是操作系统用于区分各个文件的一种内部名称。
    
    类型：指明文件的类型.
    
    位置：文件存放的路径(让用户使用)、在外存中的地址(操作系统使用，对用户不可见)
    
    大小：指明文件大小
    
    创建时间、上次修改时间、文件所有者信息
    
    保护信息：对文件进行保护的访问控制信息
  - 操作系统向上提供哪些功能
    
    创建文件(create系统调用)
    
    删除文件(delete 系统调用)
    
    读文件(read系统调用)
    
    写文件(write系统调用)
    
    打开文件(open系统调用)
    
    关闭文件(close 系统调用)
  - 文件内部应该如何被组织起来(文件的逻辑结构)
  - 文件之间应该如何被组织起来(目录结构)
  - 文件应如何存放在外存中(文件的物理结构)
  - 操作系统如何管理外存中的空闲块(存储空间的管理)
  - 操作系统需要提供的其他文件管理功能
    
    文件共享
    
    文件保护
- 02 文件的逻辑结构
  - 无结构文件
  - 有结构文件
    
    顺序文件
    
    串结构：记录顺序与关键字无关
    
    顺序结构：记录按关键字顺序排列
    
    可变长记录的顺序文件无法实现随机存取，定长记录可以
    
    定长记录、顺序结构的顺序文件可以快速检索(根据关键字快速找到记录)
    
    最大缺点：不方便增加/删除记录
    
    索引文件
    
    建立一张索引表，每个记录对应-个表项。各记录不用保持顺序,方便增加删除记录
    
    索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
    
    若索引表按关键字顺序排列，则可支持快速检索
    
    解决了顺序文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间
    
    索引顺序文件
    
    将记录分组，每组对应-一个索引表项
    
    检索记录时先顺序查索引表，找到分组，再顺序查找分组
    
    当记录过多时，可建立多级索引表
- 03 文件目录
  - 文件控制块(实现文件目录的关键数据结构)
    
    一个文件对应一个FCB，个FCB就是一个目录项，多个FCB组成文件目录
    
    对目录的操作:搜索、创建文件、删除文件、显示文件、修改文件
  - 目录结构
    
    单级目录结构
    
    一个系统只有一张目录表，不允许文件重名
    
    两级目录结构
    
    不同用户的文件可以重名，但不能对文件进行分类
    
    多级目录结构(树形目录结构)
    
    不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
    
    系统根据“文件路径"找到目标文件
    
    从根目录出发的路径是“绝对路径" ("/照片/2015-08/自拍jipg")
    
    从"当前目录”出发的路径是"相对路径”("/照片/201 5-08/自拍jpg")
    
    无环图目录结构
    
    在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图
    
    为共享结点设置一个共享计数器，计数器为0时才真正删除该结点
  - 索引结点(对文件控制块的优化)
    
    除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引结点
    
    目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减小
    
    由于目录项长度减小，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/0的次数就少了很多
- 04 文件的物理结构（文件分配方式）
  - 对非空闲磁盘块的管理（存放了文件数据的磁盘块）
    
    连续分配
    
    链接分配
    
    链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
    
    隐式链接
    
    隐式链接——除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
    
    优点：很方便文件拓展，不会有碎片问题，外存利用率高。
    
    缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。
    
    题目中没有要求，默认是隐式链接的链接分配
    
    显式链接
    
    把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表(FAT， File Allocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
    
    优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
    
    缺点：文件分配表的需要占用一定的存储空间。
    
    索引分配
    
    ①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点:若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。
    
    ②多层索引：建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+ 1次读磁盘操作。
    
    缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。
    
    ③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。
    
    优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。
    
    超级超级超级重要考点:
    
    ①要会根据多层索引、混合索引的结构计算出文件的最大长度(Key：各级索引表最大不能超过一个块) ；
    
    ②要能自己分析访问某个数据块所需要的读磁盘次数(Key：FCB中会存有。指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件——顶级索引块是否已调入内存)
    
    各种文件分配方式的区别
  - 对空闲磁盘块的管理
- 06 逻辑结构vs物理结构
  - 逻辑结构
    
    用户(文件创建者)的视角看到的亚子
    
    在用户看来，整个文件占用连续的逻辑地址空间
    
    文件内部的信息组织完全由用户自己决定，操作系统并不关心
  - 物理结构
    
    由操作系统决定文件采用什么物理结构存储
    
    操作系统负责将逻辑地址转变为(逻辑块号，块内偏移量)的形式，并负责实现逻辑块号到物理块号的映射
- 07 文件存储空间管理
  - 存储空间的划分与初始化
    
    文件卷(逻辑卷)的概念
    
    为磁盘分区（C/D/E盘），分为逻辑磁盘
    
    目录区与文件区
    
    目录区，主要存放文件目录信息（FCB）、用与磁盘存储空间管理的信息
    
    文件区，用于存放文件数据
    
    多个物理磁盘也可以组成一个文件卷
    
    初始化
    
    将各个文件卷划分为目录区、文件去
  - 几种管理方法
    
    注意：
    
    用什么方式记录、组织空闲块？
    
    如何分配磁盘块
    
    如何回收磁盘块
    
    空闲表法
    
    绿色为空闲块、橙色为非空闲块，适用于“连续分配方式”
    
    如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
    
    如何回收磁盘块:与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况
    
    ①回收区的前后都没有相邻空闲区;
    
    ②回收区的前后都是空闲区;
    
    ③回收区前面是空闲区;
    
    ④回收区后面是空闲区。
    
    总之，回收时需要注意表项的合并问题。
    
    空闲链表法
    
    空闲盘块链
    
    以盘块为单位组成一条空闲链
    
    图示
    
    空闲盘区链
    
    以盘区为单位组成一条空闲链
    
    图示
    
    如何分配：如何分配:若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
    
    如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
    
    离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。
    
    两种分配方式的图示
    
    位示图法
    
    位示图：每个二进制位对应一一个盘块。在本例中，“0” 代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每- -位对应一一个盘块。因此可以用(字号，位号)对应一个盘块号。当然有的题目中也描述为(行号，列号)
    
    计算：
    
    通过（字号，位号）=（i， j）定位得到盘块号b
    
    b号盘块对应的字号i = b/n，位号j = b%n
    
    区分从0开始还是从1开始
    
    如何分配：若文件需要K个块，
    
    ①顺序扫描位示图，找到K个相邻或不相邻的“0”;
    
    ②根据字号、位号算出对应的盘块号，将相应盘块分配给文件;
    
    ③将相应位设置为“1”
    
    如何回收：
    
    ①根据回收的盘块号计算出对应的字号、位号;
    
    ②将相应二进制位设为“0”
    
    适用：连续分配和离散分配都适用
    
    成组链接法
    
    Unix系统中采用了成组链接法对磁盘空闲块进行管理
    
    文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存，并且要保证内存与外存的“超级块”数据一致
    
    超级块
    
    还有点...笔者理解起来有点困难，先不写了...
  - 08 文件的基本操作
    
    向上提供的几个最基本的功能
    
    创建文件 create系统调用
    
    点击“新建”后，图形化交互进程在背后调用“create系统调用”
    
    提供的参数
    
    所需的外存空间大小：1KB
    
    文件存放路径"D:/Demo"
    
    文件名 test.txt
    
    操作系统需要做的：
    
    在外存找到文件所需的空间（用空闲链表法、位示图、成组链接法等管理策略，找到空闲空间）
    
    根据文件存放路径的信息找到该目录对应的目录文件(此处就是D:/Demo目录)，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。
    
    删除文件 delete系统调用
    
    读文件 read系统调用
    
    写文件 write系统调用
    
    打开文件open系统调用
    
    关闭文件 close系统调用
- 0x...
第五章输入/输出(I/O)管理
- 后续会更新...
- 稍安勿躁。

以上内容整理于幕布文档